package sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/4/1 20:57
 */
public class leetcode215数组第K个最大元素 {

    /*
    暴力做法, 那可 太简单了!
    这个用对数器, 那就非常的爽了!
     */


    /*
     注意 这是 求 第 k大的元素  , 其实没必要 返回值, 直接返回下标即可
     求 第 k 大元素 和 求 第 k 小的 数字, 可以公用这个 函数,
     第  k 大, 就是求 第 len - k 小的数字!
     */
    public int soulution(int nums[],int k){
        return recursion(nums,nums.length - k,0, nums.length - 1);
    }

    public int recursion(int nums[],int index,int l,int r){
        if(l == r){ // 第 k da 元素 一定 在 l ~ r 上, 那如果 都走到 l == r 了 那说明 ,l (r)位置 就是 满足的 位置!
            return nums[l];
        }
        int value = (int)(l + Math.random() * (r - l + 1));
        swap(nums,value,r);
        /*
         此时的 partition 返回的 是 等于 = 区域的  left 和 right 边界!
         这一点,一定要搞清楚!, 这个 partition ,这是 核心,
         荷兰国旗问题, 一定要整明白!
         */
        int[] partitation = partitation(nums, l, r);
        if(index >= partitation[0] && index <= partitation[1]){
            return nums[index];
        }else if(index < partitation[0] ){
            return recursion(nums,index,l,partitation[0] - 1);
        }else{
            return recursion(nums,index,partitation[1] + 1,r);
        }
//        return 1;
    }

    public void swap(int nums[],int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    public int[] partitation(int nums[],int l,int r){
//        System.out.println(nums[r]);
        int less = l - 1,more = r,index = l;
        while(index < more){
            if(nums[index] < nums[r]){
                swap(nums,++less,index++);
            }else if(nums[index] == nums[r]){
                index++;
            }else{
                swap(nums,index,--more);
            }
        }
        swap(nums,more,r);
        return new int[]{less + 1,more};
    }


    public int rightFunction(int nums[],int k){
        Arrays.sort(nums);
        return nums[nums.length - k];
    }



    /**
     * 首先生成 随机数组的函数！
     *
     * @param arraySize 数组的大小（根据 题目的 不同， 也可能是 一个数组的  最大长度， 随机生成 数组的 长度 在 1 ~  arraySize 之间）
     * @param max       数组中元素的最大值
     * @param min       一个指标， 如果 min = 0， 代表 数组中的元素，>=0 ，min = 1， 代表 全是正数  min = -1 ，可正 ke 负 ， 可为 0
     * @param fix       如果 fix = true 代表， 数组的长度 固定， 反之， 数组的长度 不固定
     * @return 一个 生成的随机的数组(长度可以随机， 也可以 固定， 看具体题目的要求)
     */
    public int[] ramdomArray(int arraySize, int max, int min, boolean fix) {
        int ramdomArraySize = fix ? arraySize : (int) (Math.random() * (arraySize + 1)) + 1; // 数组的长度 , 由fix 来控制 是否随机
        int arr[] = new int[ramdomArraySize];
        if (min == 0) {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max + 1)); // arr[i] = [0 , max]
            }
        } else if (min == 1) {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max)) + 1;//  arr[i] =  [1 , max + 1)
            }
        } else {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max + 1) - Math.random() * (max + 1)); // 可正 可 负 可为 0
            }
        }
        return arr;
    }


    public void testRight() {
        int testTimes = 20000; // 自己写！
        int arraySize = 6;
        int max = 20;
        int min = -1;
        boolean fix = false;
        boolean isSuccess = true;
        for(int i = 0;i <  testTimes;i++){
            int[] ints = ramdomArray(arraySize, max, min, fix);
            int arr1[] = Arrays.copyOf(ints, ints.length);
            int arr2[] = Arrays.copyOf(ints, ints.length);
            int k = (int)(Math.random() * (arr1.length) - 1) + 1;
//            System.out.println(arr1.length + " " + k);
            // 你的方法
            int ans1 = soulution(arr1, k);
            int ans2 = rightFunction(arr2, k);
//            int[] ans1 = partition(arr1, 0,arr1.length - 1,arr2[k]);
//            int[] ans2 = partition(arr2, 0,arr2.length - 1,arr2[arr2.length - 1]);
//            System.out.println(Arrays.toString(arr2));
//            absoluteRightFunction(arr2);
            if(ans1 != ans2){
                 /*
                  说明 有问题， 可以打印下，数组，看下是什么 问题！
                  */
                isSuccess = false;
                Arrays.sort(ints);
                System.out.println(k);
                System.out.println(Arrays.toString(ints));
                System.out.println(ans1 + "   " + ans2);
            }
        }
        System.out.println(isSuccess ? "success" : "fuck!");
    }



    @Test
    public void test(){
        testRight();
//        for(int  i = 0;i < 10;i++){
//            int l = 10,r = 20;
//            System.out.println((l + (int)(Math.random() * (r - l + 1))));
//            System.out.println((int)(l + Math.random() * (r - l + 1)));
//            System.out.println("    ");
//        }

    }







}
